In the field of computer storage, errors can occur when storing, transmitting, or receiving digital signals. These errors are practically unavoidable due to inherent noise present on the transmission media and the storing/receiving systems. To mitigate these errors, several methods, such as, for example, Reed Solomon coding, have been developed to detect and correct errors.
In the field of computer storage, there exists many Redundant Arrays of Inexpensive Disks (RAID) controller designs, most of which focus on RAID system design software and hardware techniques. The simple and basic way to RAID a system and prevent data lost is the “RAID level 1” configuration which simultaneously writes data to two storage units. The second storage unit is used to mirror the data store and used in the 1st storage unit; however this is very costly as 50% of the available storage units are used for backup storage.
As technology evolves with its plethora of small, inexpensive storage units with high storage capacity and high bandwidth, the technique of distributing data among multiple storage devices to achieve high bandwidth input/output with one or more error-correcting algorithms becomes increasingly important. The “RAID level 5” configuration, also called the “N+1 parity” technique, provides a simple solution to calculate the checksum by performing bitwise exclusive-or (XOR) of the data bytes distributed to all storage devices. If one of the N+1 devices fails, the data can be reconstructed by XOR-ing the data of the remaining N devices. N+1 parity is attractive because of its simplicity; however, it requires one extra storage device and one extra write operation per write to any single device. Its main disadvantage is that it cannot recover from more than one simultaneous storage device failure.
The “RAID level 6” configuration, or “p+q parity” technique, provides better error recovery by not only generating P checksum parity (p parity) as defined in RAID level 5, but also generating Q checksum parity (q parity) by adopting an error correction algorithm through Galois Field (GF) multiplication with a primitive polynomial. If any two of the N+2 devices fails, the failing devices can be reconstructed by using the P and Q checksums together with the remaining N devices. Generally, there are several known primitive polynomials available for GF multiplication with corresponding circuit implementations and methods that are either complicated or expensive to run or unavailable to for use.
As mentioned above, GF arithmetic is widely used in communication systems for Reed Solomon coding and also in Advanced Encryption Standard (AES) coding. While GF addition operations are straightforward, the same cannot be said of GF multiplication operations. The following provides an overview of GF operations.
GF arithmetic is a cyclic finite field arithmetic meaning that any operation performed on any two numbers within the field yields a number in the field, i.e., there is no arithmetic operation that can be done on any two numbers within the field that will produce a number outside of the field. Since digital systems transmit/store data in bits, which can only take on one of two values (0 or 1), grouping these bits together to build a symbol is common in digital systems and these groupings are all based on powers of two. Table 1 shows the relationship between the number of bits per symbol, the equivalent range of integers spanned by the number of bits, and the equivalent GF representation.
TABLE 1Digital symbols vs. GF notationNumber of bits Galois Field per symbolRange of integersrepresentation10 to 1GF(2)20 to 3GF(4)30 to 7GF(8)40 to 15GF(16)50 to 31GF(32)60 to 63GF(64)70 to 127GF(128)80 to 255GF(256)m0 to (2m − 1)GF(2m)
Galois field arithmetic uses the numbers shown in Table 1. For example, the range of integers from 0 to 7 (0, 1, 2, 3, 4, 5, 6, 7) has a Galois Field representation or notation of GF(8) because the Galois Field has 8 elements, while the range of integers 0 to 1 has a Galois Field of GF(2) because it has only two elements, etc.
There are many ways of representing numbers in the finite field of any given GF. Table 2 illustrates such representations of the values of the GF(8) in integer, binary and vector (or polynomial) formats.
TABLE 2Representation of GF(8)IntegerBinaryPolynomial00000100112010x3011x + 14100x25101x2 + 16110x2 + x7111x2 + x + 1
In addition, each GF can have one or more primitive polynomials, also called generator polynomials, which is analogous to a particular set of consecutive real integers. These one or more primitive polynomials include one or more prime numbers, depending upon how large is the particular set of consecutive integers. The primitive polynomials, p(x), are used to define the arithmetic functions for each GF and to ensure that each GF arithmetic operation yields a result that is part of the GF in question. For example, in GF arithmetic, as in basic arithmetic, certain mathematical properties, such as, for example, commutativity and associativity exist. Therefore, if upon determining the sum or product of any two elements within a GF, the sum or product lies outside the GF, the sum or product in question is divided by a predetermined primitive polynomial in order to preserve the GF. Table 3 lists the integer representation of known primitive polynomials for GF(8) to GF(256).
TABLE 3Primitive polynomials for Galois FieldsGF(x)P(x)GF(x)P(x)GF(x)P(x)811128137256285161912814325636132371281572564873261128247256299325512819125635764671282132563556410312813125635164109128203256451128229
As shown in Table 3, there is only one primitive polynomial for GF(8) and one primitive polynomial for GF(16); this is due to the smallness of the fields in question. Respectively, the primitive polynomials are represented by the decimal number 11 (1011 binary, x3+x+1 polynomial) and by the decimal number 19 (10011 binary, x4+x+1 polynomial). However, GF(128) has 9 primitive polynomials and GF(256) has 8 primitive polynomials. For example, a primitive polynomial for GF(256) is 285, which corresponds to the binary number 100011101, which has the corresponding polynomial p(x)=x8+x4+x3+x2+1.
In general, for a given GF(2m) field, there exists at least one primitive polynomial which yields a multiplication result in the GF(2m) field. As the number of m-bit increases, the number of available primitive polynomials also increases. Galois field multiplication is difficult and time consuming for traditional digital signal processors (DSP) to perform. However, for certain data storage or encryptions systems, it may be a requirement to support multiple primitive polynomials.
Several approaches have been used in GF multiplication operations. These include a brute force approach where a GF multiplier design is simplified by using a pre-determined, fixed primitive polynomial. These types of approaches aim at reducing hardware logic, can be easily implemented and are typically used in AES encryption or Reed Solomon coding. With a given fix primitive polynomial, logic gates are easily defined and a GF multiplier design can be implemented by defining a related equation used to multiply all components of any two given input polynomials. Such approaches are usually slow.
The most commonly used approach in multiplying two values of a GF is to generate two logarithm tables, which converts the multiplication process into three lookup tables and an addition. These tables can be referred to as gflog[ ] (GF logarithm) and gfilog[ ] (GF inverse logarithm). The gflog[ ] table is defined for the indices 1 to 2m−1, and maps the index to its logarithm in the GF. As for the gfilog[ ] table, it is defined for the indices 0 to 2m−2, and maps the index to its inverse logarithm in the GF. The tables obey the rules gflog[gfilog[x]]=x, and gfilog[gflog[x]]=x. With these tables, it is possible to multiply two elements of GF(2m) by adding their logs and then taking the inverse log, which yields the product. The advantage of using the table lookup approach is that it supports all kinds of primitive polynomial by simply updating the lookup tables with different index mapping values. However, this approach is similar to the brute approach in that it is quite slow.
It is, therefore, desirable to provide a GF multiplier system and method that is fast and that can function with any arbitrary primitive polynomial.